#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
//单链表的声明
typedef struct LNode
{
    ElemType data;//存储元素的数据域
    struct LNode *next;//存储后继节点
}LinkNode;
//建立单链表
//1）头插法，每次插入表头，L，an,an-1,an-2``````a2,a1
void CreateListF(LinkNode *&L,ElemType a[],int n)
{
    LinkNode *s;
    L=(LinkNode *)malloc(sizeof(LinkNode));//给L分配内存用malloc
    L->next=NULL;//初始化链表
    for(int i=0;i<n;i++)
    {
        s=(LinkNode *)malloc(sizeof(LinkNode));//给s结点指针分配内存
        s->data=a[i];//将数组值给s
        s->next=L->next;//插入操作
        L->next=s;
    }
}
//2)尾插法
void CreateListR(LinkNode *&L,int n,ElemType a[])
{
    LinkNode *s,*r;//定义头指针和尾指针
    L=(LinkNode *)malloc(sizeof(LinkNode));//分配内存
    r=L;
    for(int i=0;i<n;i++)
    {
        s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=a[i];
        r->next=s;
        r=s;
    }
    r->next=NULL;
}
//初始化单链表
void InitList(LinkNode *&L)
{
    L=(LinkNode *)malloc(sizeof(LinkNode));
    L->next=NULL;
}
//销毁单链表
void DestroyList(LinkNode *&L)
{
    LinkNode *pre=L,*p=L->next;
    while(p!=NULL)
    {
        free(pre);
        pre=p;
        p=pre->next;
    }
    free(pre);
}
//判断是否为空链表
bool ListEmpty(LinkNode *L)
{
    return(L->next==NULL);
}
//求线性表的长度
int ListLength(LinkNode *L)
{
    int n=0;
    LinkNode *p=L;
    while(p->next!=NULL)
    {
        n++;
        p=p->next;
    }
    return(n);
}
//输出线性表
void DisList(LinkNode *L)
{
    LinkNode *p=L->next;
    while(p!=NULL)
    {
        printf("%d",p->data);
        p=p->next;
    }
    printf("\n");
}
//按序号求线性表的元素
bool GetElem(LinkNode *L,int i,ElemType &e)
{
    int j=0;
    LinkNode *p=L;
    if(i<=0)
        return false;
    while(j<i && p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return false;
    else
        e=p->data;
        return true;
}
//按元素值查找
int LocateList(LinkNode *L,ElemType e)
{
    int i=1;
    LinkNode *p=L->next;
    while(p!=NULL)
    {
        p=p->next;
        i++;
    }
    if(p==NULL)
        return(0);
    else
        return(i);
}
//插入数据元素
bool ListInsert(LinkNode *&L,int i,ElemType e)
{
    int j=0;
    LinkNode *p=L,*s;
    if(i<=0) 
        return false;
    while(j<i-1 && p!=NULL)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    else
       {
        s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=e;
        s->next=p->next;
        p->next=s;
        return true;
       }
}
//删除数据元素
bool ListDelete(LinkNode *&L,int i,ElemType &e)
{
    int j=0;
    LinkNode *p=L,*q;
    if(i<=0)
        return false;
    while(j<i-1 && p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return false;
    else
    {
        q=p->next;
        if(q==NULL)
            return false;
        e=q->data;
        p->next=q->next;
        free(q);
        return true;
    }
}
//应用
//将L分成两个单链表L1，L2，L1使用L的头节点
void split(LinkNode *&L,LinkNode *&L1,LinkNode *&L2)
{
    LinkNode *p=L->next,*q,*r1;
    L1=L;//将L的头结点给L1
    L2=(LinkNode *)malloc(sizeof(LinkNode));//创建L2的头结点
    L2->next=NULL;//初始化头结点
    while(p!=NULL)
    {
        r1->next=p;//L1采用尾插法
        r1=p;
        p=p->next;//将数据后移一个指针，到b
        q=p->next;
        p->next=L2->next;//L2用头插法
        L2->next=p;
        p=q;
    }
    r1->next=NULL;
}
//删除元素值最大的元素
void delmaxnode(LinkNode *&L)
{
    LinkNode *p=L->next,*pre=L,*maxp=p,*maxpre=pre;
    while(p!=NULL)
    {
        if(maxp->data<p->data)//如果maxp的值小于p，将p的值给maxp，pre的值给maxpre
        {
            maxp=p;
            maxpre=pre;
        }
        pre=p;//将pre和p的值后移一位
        p=p->next;
    }
    maxpre->next=maxp->next;//进行删除操作
    free(maxp);
}
//递增排序
void sort(LinkNode *&L)
{
    LinkNode *p,*pre ,*q;
    p=L->next->next;
    L->next->next=NULL;
    while(p!=NULL)
    {
        q=p->next;
        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)//若pre的值小于p，则不用交换，将pre的位置后移一位
            pre=pre->next;
        p->next=pre->next;//进行头插操作
        pre->next=p;
        p=q;
    }
}
int main()
{
    LinkNode *h;
    ElemType e;
    printf("1)初始化单链表\n");
    InitList(h);
    printf("2)采用尾插法插入元素\n");
    ListInsert(h,1,'a');
    ListInsert(h,2,'b');
    ListInsert(h,3,'c');
    ListInsert(h,4,'d');
    ListInsert(h,5,'e');
    printf("3)输出单链表\n");
    DisList(h);
    printf("4)单链表长度%d\n",ListLength(h));
    printf("5)单链表%s\n",(ListEmpty(h)?"空":"非空"));
    GetElem(h,3,e);
    printf("6)单链表第三个元素\n",e);
    printf("7)元素a的位置%d\n",LocateList(h,'a'));
    printf("8)在第四个元素位置上插入元素\n");
    ListInsert(h,4,'f');
    printf("9)输出单链表\n");
    DisList(h);
    printf("10)删除第三个元素\n");
    ListDelete(h,3,e);
    printf("11)输出单链表\n");
    DisList(h);
    printf("12)释放单链表\n");
    DestroyList(h);
    return 1;
}